package com.jeff.huawei.practice;

public class ChampagneTower {
    public static double champagneTower(int poured, int query_row, int query_glass) {
        // 定义一个二维数组 dp，其中 dp[i][j] 表示第 i 行第 j 个杯子的香槟量
        double[][] dp = new double[101][101]; // 最多需要 100 层，额外留空间
        dp[0][0] = poured; // 初始时，将香槟倒入第 0 行第 0 个杯子

        // 动态规划计算每个杯子的香槟量
        for (int i = 0; i <= query_row; i++) { // 遍历每一行
            for (int j = 0; j <= i; j++) { // 遍历每一行的每个杯子
                // 如果当前杯子的香槟量超过 1，则进行溢出计算
                if (dp[i][j] > 1) {
                    double overflow = dp[i][j] - 1; // 溢出的香槟量
                    dp[i][j] = 1; // 当前杯子装满
                    dp[i + 1][j] += overflow / 2; // 向左下方杯子流动
                    dp[i + 1][j + 1] += overflow / 2; // 向右下方杯子流动
                }
            }
        }

        // 返回目标杯子的香槟量比例（最多为 1）
        return Math.min(dp[query_row][query_glass], 1.0);
    }

    public static void main(String[] args) {
        // 示例 1
        int poured = 4;
        int query_row = 2;
        int query_glass = 1;
        System.out.println("香槟比例：" + champagneTower(poured, query_row, query_glass)); // 输出: 0.5

        // 示例 2
        poured = 1;
        query_row = 1;
        query_glass = 1;
        System.out.println("香槟比例：" + champagneTower(poured, query_row, query_glass)); // 输出: 0.0
    }
}
